package a15_MapAndSet;

/**
 * @Author quan
 * @Description HashMap的实现（基于int开散列方案的哈希表）:主要由数组和链表构成
 * @Date 2023/4/8 21:40
 */
public class MyHashMap {
    //数组的每个元素存储的是链表，链表的每个节点存储自身的值和指向下一个节点的地址，而自身的值是一个键值对key和value组成
    //定义内部的Node
    private static class Node{
        int key;
        int value;
        Node next;
        //构造方法
        Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    //定义 保存链表的数组，所以数组的类型是Node[]
    private Node[] data;
    //定义 当前哈希表中有效元素的个数：数组
    private int size;
    //定义 计算哈希函数的取模数
    private int M;
    //定义 负载因子值
    private static final double LOAD_FACTOR = 0.75;

    //构造方法
    public MyHashMap(){
        this(16);
    }
    public MyHashMap(int capacity){
        this.data = new Node[capacity];//确定数组大小
        this.M = capacity;//为方便起见，将M取为capacity值大小
    }
    /**
     * 判断当前HashMap中是否包含指定的key值
     */
    public boolean containsKey(int key){
        //1、通过哈希函数计算key值在数组中的索引位置
        int index = hashFun(key);
        //2、走到索引位置上，然后遍历该位置上的链表，判断链表中是否含有该元素
        for (Node x = data[index]; x != null ; x = x.next) {
            if(x.key == key){
                return true;
            }
        }
        return false;
    }
    /**
     * 判断当前函数中是否含有指定的value值
     */
    public boolean containValue(int value){
        int index = hashFun(value);
        for (int i = 0; i < data.length; i++) {
            //->内层循环就是每个子链表的遍历
            for (Node x = data[i]; x != null ; x = x.next) {
                if(x.value == value){
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * 疑问：为什么key值就是索引位置下的链表，而value值的话要数组下的所有的链表都遍历呢？
     */

    /**
     * 增：在哈希表中增加一对新元素，如果存在则返回添加前的值；如果是新元素则返回-1
     */
    public int put(int key,int value){
        //1、计算当前元素的索引下标
        int index = hashFun(key);
        //2、在当前的子链表中判断key值是否存在，如果存在，则只修改value值即可
        for (Node x = data[index]; x != null; x = x.next) {
            if(x.key == key){
                //说明key值存在，记录旧的value值并修改该值
                int oldValue = x.value;
                x.value = value;
                return oldValue;
            }
        }
        //3、如果key是第一次出现，则将这个<key,value>的节点头插到当前的子链表中
        //先将该<key,value>的节点产生
        Node node = new Node(key,value);
        //---------------这两步相想不出来具体细节✉✉✉✉✉✉✉？--------------
        node.next = data[index];
        data[index] = node;
        size++;
        //4、增加元素之后，要判断当前哈希表的冲突情况，判断是否需要扩容
        if(size >= data.length * LOAD_FACTOR){//-----------------✉✉✉✉✉✉✉公式
            resize();//-----------------✉✉✉✉✉✉多看几遍
        }
        return -1;
    }
    /**
     * 判断元素是否需要扩容？扩容就是创建一个是原数组n(比如n=2)倍大小的一个新数组，然后将元素值都拷贝过来
     */

    private void resize() {
        //M是哈希函数的取模数：扩大2倍
        this.M = data.length << 1;
        //创建一个新数组
        Node[] newData = new Node[data.length << 1];
        //将原数组的值都搬移到新数组中
        for (int i = 0; i < data.length; i++) {//取到数组的每一个索引
            for (Node x = data[i]; x!= null;) {//数组的每一个索引位置对应的值就是一个链表：遍历链表
                //先记录下该节点的下一个节点，防止丢失
                Node next = x.next;
                //将当前x节点搬移到新数组的对应位置：该索引位置要重新通过HashFun计算
                int newIndex = hashFun(x.key);
                //将该旧节点头插到新数组的对应位置
                x.next = newData[newIndex];//--------这两行不懂-✉✉✉✉✉✉✉？ 将该节点与数组的索引位置（也就是链表的头结点）连接起来
                newData[newIndex] = x;//更新该数组的索引位置：链表的头结点为该x节点
                //继续搬移原数组的下一个节点
                x = next;
            }
        }
        //更新data的指向
        data = newData;
    }
    /**
     * 在当前HashMap中删除指定的key值
     */
    public boolean removeKey(int key){
        //1、先将key值经过Hash函数计算求出key值
        int index = hashFun(key);
        //2、判断该值是否存在，不存在则直接返回false;如果存在则要删除
        if(data[index] == null){
            return false;
        }
        //说明该key值存在：链表的删除方式
        //如果刚好是链表头结点的删除
        if(data[index].key == key){
            data[index] = data[index].next;
            size--;
            return true;
        }
        //否则遍历该链表，从链表中找到该key值所在的节点删除
        Node x = data[index];
        while (x.next!=null){
            if(x.next.key == key){
                x.next = x.next.next;
                size--;
                return true;
            }
        }
        //否则说明该key值不存在，返回false
        return false;
    }
    //自定义的哈希函数
    private int hashFun(int key) {
        return key % M;
    }

}
